home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 155_01 / btree1.c < prev    next >
C/C++ Source or Header  |  1990-10-07  |  16KB  |  436 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <alloc.h>
  4. #include "btree.h"
  5.  
  6. /* Author: Ray Swartz
  7.  *         Berkeley Decision/Systems, Inc.
  8.  *         P.O. Box 2528
  9.  *         Santa Cruz, Calif. 95063
  10.  * Last Modified: 4/28/85
  11.  *
  12.  * ANY USE OF THESE LIBRARY ROUTINES EITHER PERSONAL OR COMMERCIAL
  13.  * IS ALLOWED UPON THE CONDITION THAT THE USER IDENTIFY THEM
  14.  * AS BEING USED IN THE PROGRAM.  IDENTIFYING INFORMATION MUST
  15.  * APPEAR IN THE PROGRAM DOCUMENTATION OR ON THE TERMINAL SCREEN.
  16.  *
  17.  *         #################################    
  18.  *         # UNATTRIBUTED USE IS FORBIDDEN #
  19.  *         #################################
  20.  *
  21.  * The insert routine was directly translated from the algorithm
  22.  *  in D. Knuth's Volume 3 of The Art of Computer Programming
  23.  *  (Sorting and Searching) pages 455 - 457.  Single letter
  24.  *  variables (p, q, r, s) are used to make the algorithm steps
  25.  *  more obvious.
  26.  */
  27. /*
  28.  *    Modifier: Honma Michimasa
  29.  */
  30.  
  31. /**** Function prot. ********/
  32. int insert(char *argkey, long recnbr, struct keyinfo *fileinfo);
  33.                  /* insert key (argkey) into tree */
  34. void link(int alpha1, struct node *node1, int alpha2, struct node *node2);
  35. void nbr_link(long *nbr, int alpha, struct node *node1);
  36.                  /* set a record number according to alpha */
  37. void link_nbr(int alpha, struct node *node1, long nbr);
  38.                  /* set a link according to alpha */
  39. void node_bal(int alpha, struct node *node1, struct node *node2, struct node *node3);
  40.                   /* node balancing in Step A9 */
  41. void delete_key(long node_nbr, struct node *current_node, struct keyinfo *fileinfo);
  42. int get_next(long *node_nbr, struct node *current_node, struct keyinfo *fileinfo);
  43.                   /* retrieve next higher node */
  44. int find_key(char *key1, long *node_nbr, struct node *current_node, struct keyinfo *fileinfo);
  45.                  /* locate a key */
  46.  
  47.  
  48.  
  49. int insert(char *argkey, long recnbr, struct keyinfo *fileinfo) /* insert key (argkey) into tree */
  50. /* struct keyinfo *fileinfo;  file to insert key into */
  51. /* char *argkey;     key to insert */
  52. /* long recnbr;      record number of corresponding data record */
  53. {
  54.     static long top;  /* where balancing will have to take place, if at all */
  55.     static long p_rec;
  56.     static long s_rec;
  57.     static long q_rec;
  58.     static long r_rec;
  59.     static struct node q_node, s_node, r_node, p_node;
  60.     static int alloc_flag = NO;  /* flag for pointer space allocation */
  61.     int compare;   /* holds key comparison values */
  62.     
  63.     if (fileinfo->next_avail >= MAX_NODES) {
  64.         printf("Only %d nodes allowed in a keyfile\n");
  65.         exit(1);
  66.     }
  67.     if(alloc_flag == NO) {   /* set up key pointers in node structures  */
  68.         q_node.key = malloc(fileinfo->keylength + 1); /* first call to */
  69.         s_node.key = malloc(fileinfo->keylength + 1); /* insert function */
  70.         p_node.key = malloc(fileinfo->keylength + 1);
  71.         r_node.key = malloc(fileinfo->keylength + 1);
  72.         alloc_flag = YES;
  73.     }
  74.     if (fileinfo->list_head == 0) {   /* no records in list */
  75.         fileinfo->list_head = 1;  /* insert key as head of list */
  76.         p_node.balance = p_node.right_link = p_node.left_link = 0;
  77.         p_node.delete_flag = NO;
  78.         p_node.rec_nbr = recnbr;
  79.         strcpy(p_node.key, argkey);
  80.         write_node(1L, &p_node, fileinfo);
  81.         fileinfo->next_avail++;
  82.         fileinfo->nbr_in_list++;
  83.         return(YES);
  84.     }
  85.     top = TOP;    /* initialize to see if list head changes */
  86.     p_rec = fileinfo->list_head;   /* Step A1 (find spot to insert) */
  87.     s_rec = fileinfo->list_head;
  88.     while(1) {
  89.         get_node(p_rec, &p_node, fileinfo);
  90.         if ((compare = strcmp(argkey, p_node.key)) < 0) {  /* Step A2 */
  91.             q_rec = p_node.left_link;  /* Step A3 (move left) */
  92.             if (q_rec == END) {  /* insert here */
  93.                 q_rec = fileinfo->next_avail++;
  94.                 p_node.left_link = q_rec;
  95.                 break;  /* loop exit */
  96.             }
  97.             else {  /* look again from this node */
  98.                 get_node(q_rec, &q_node, fileinfo);
  99.                 if (q_node.balance != 0) {
  100.                     top = p_rec;
  101.                     s_rec = q_rec;
  102.                 }
  103.             }
  104.             p_rec = q_rec;
  105.         }
  106.         else  {  /* Step A4 (move right) */
  107.             q_rec = p_node.right_link;
  108.             if (q_rec == END) {  /* insert here */
  109.                 q_rec = fileinfo->next_avail++;
  110.                 p_node.right_link = q_rec;
  111.                 break;  /* loop exit */
  112.             }
  113.             else {  /* look again from this node */
  114.                 get_node(q_rec, &q_node, fileinfo);
  115.                 if (q_node.balance != 0) {
  116.                     top = p_rec;
  117.                     s_rec = q_rec;
  118.                 }
  119.                 p_rec = q_rec;
  120.             }
  121.         }
  122.     } /* end of while loop */
  123. /* Step 5 (insert key at q_node) */      
  124.     q_node.left_link = q_node.right_link = END;
  125.     q_node.balance = 0;
  126.     q_node.delete_flag = NO;
  127.     q_node.rec_nbr = recnbr;
  128.     strcpy(q_node.key, argkey);
  129.     if (write_node(q_rec, &q_node, fileinfo) == NO)
  130.         return(NO);  /* write failed */
  131.     write_node(p_rec, &p_node, fileinfo);
  132.     get_node(s_rec, &s_node, fileinfo); /* Step A6 (adjust balance factors) */
  133.     if (strcmp(argkey, s_node.key) < 0)
  134.         r_rec = p_rec = s_node.left_link;
  135.     else
  136.         r_rec = p_rec = s_node.right_link;
  137.     while (p_rec != q_rec) {
  138.         get_node(p_rec, &p_node, fileinfo);
  139.         if(strcmp(argkey, p_node.key) < 0) {
  140.             p_node.balance = -1;
  141.             write_node(p_rec, &p_node, fileinfo);
  142.             p_rec = p_node.left_link;
  143.         }
  144.         else {
  145.             p_node.balance = 1;
  146.             write_node(p_rec, &p_node, fileinfo);
  147.             p_rec = p_node.right_link;
  148.         }
  149.     }
  150.     compare = (strcmp(argkey, s_node.key) < 0) ? -1 : 1; /* Step A7 */
  151.     if (s_node.balance == 0) {  /* Step A7i */
  152.         fileinfo->nbr_in_list++;
  153.         s_node.balance = compare;
  154.         write_node(s_rec, &s_node, fileinfo);
  155.         return(YES);
  156.     }
  157.     else if(s_node.balance == -compare) {  /* Step A7ii */
  158.         fileinfo->nbr_in_list++;
  159.         s_node.balance = 0;
  160.         write_node(s_rec, &s_node, fileinfo);
  161.         return(YES);
  162.     }
  163.     else { /* Step A7iii (tree out of balance) */
  164.         fileinfo->nbr_in_list++;
  165.         get_node(s_rec, &s_node, fileinfo);
  166.         get_node(r_rec, &r_node, fileinfo);
  167.         if (r_node.balance == compare) { /* Step A8 (single rotate) */
  168.             p_rec = r_rec;
  169.             link(compare, &s_node, -compare, &r_node);
  170.             link_nbr(-compare, &r_node, s_rec);
  171.             s_node.balance = r_node.balance = 0;
  172.         }
  173.         else {   /* Step A9 (double rotate) */
  174.             nbr_link(&p_rec, -compare, &r_node);
  175.             get_node(p_rec, &p_node, fileinfo);
  176.             link(-compare, &r_node, compare, &p_node);
  177.             link_nbr(compare, &p_node, r_rec);
  178.             link(compare, &s_node, -compare, &p_node);
  179.             link_nbr(-compare, &p_node, s_rec);
  180.             node_bal(compare, &p_node, &s_node, &r_node);
  181.             p_node.balance = 0;
  182.             write_node(p_rec, &p_node, fileinfo);
  183.         }
  184.         if (top == TOP)  /* Step A10 */ 
  185.             fileinfo->list_head = p_rec; /* balanced at list head */ 
  186.         else {   /* balanced at top of a sub-tree */
  187.             get_node(top, &q_node, fileinfo); 
  188.             if (s_rec == q_node.right_link)
  189.                 q_node.right_link = p_rec; 
  190.             else
  191.                 q_node.left_link = p_rec;
  192.             write_node(top, &q_node, fileinfo);
  193.         }
  194.         write_node(s_rec, &s_node, fileinfo);
  195.         write_node(r_rec, &r_node, fileinfo);
  196.         return(YES);
  197.     }
  198. }
  199.  
  200.  
  201. void link(int alpha1, struct node *node1, int alpha2, struct node *node2)
  202. /*
  203. int alpha1, alpha2;
  204. struct node *node1, *node2;
  205. */
  206. {
  207.     /* see definition of LINK(a, P) on Knuth pg. 455 (Vol. 3) */
  208.       
  209.     if (alpha1 == -1 && alpha2 == -1)
  210.         node1->left_link = node2->left_link;
  211.     else if(alpha1 == -1 &&